package cn.lbd.arithmetic.leetcode.editor.cn;
//对链表进行插入排序。
//
// 
//插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。 
//每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。 
//
// 
//
// 插入排序算法： 
//
// 
// 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 
// 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 
// 重复直到所有输入数据插入完为止。 
// 
//
// 
//
// 示例 1： 
//
// 输入: 4->2->1->3
//输出: 1->2->3->4
// 
//
// 示例 2： 
//
// 输入: -1->5->3->4->0
//输出: -1->0->3->4->5
// 
// Related Topics 排序 链表 
// 👍 251 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}

class MainClass {
    public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for(int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }

    public static ListNode stringToListNode(String input) {
        // Generate array from the input
        int[] nodeValues = stringToIntegerArray(input);

        // Now convert that list into linked list
        ListNode dummyRoot = new ListNode(0);
        ListNode ptr = dummyRoot;
        for(int item : nodeValues) {
            ptr.next = new ListNode(item);
            ptr = ptr.next;
        }
        return dummyRoot.next;
    }

    public static String listNodeToString(ListNode node) {
        if (node == null) {
            return "[]";
        }

        String result = "";
        while (node != null) {
            result += Integer.toString(node.val) + ", ";
            node = node.next;
        }
        return "[" + result.substring(0, result.length() - 2) + "]";
    }

    public static void main(String[] args) throws IOException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            ListNode head = stringToListNode(line);

            ListNode ret = new Solution147().insertionSortList(head);

            String out = listNodeToString(ret);

            System.out.print(out);
        }
    }
}

class Solution147 {
    public static ListNode insertionSortList(ListNode head) {
        ListNode listNode = new ListNode(0);
        listNode.next = head;
        //为了让LeetCode测试代码带头节点来适配我的代码，强行给[4,2,1,3]前面构造一个0
        ListNode tmp = listNode.next;
        ListNode newNode = new ListNode(0);
        //原链表当前节点的下一结点
        ListNode next = null;
        while (tmp != null) {
            //先那第一个节点到有序链表中做初始值
            if (newNode.next == null) {
                next = tmp.next;
                tmp.next = newNode.next;
                newNode.next = tmp;
                tmp = next;
                continue;
            }
            //因为tmp会在插入到有序链表时,next被修改，需要再插入前提前保存原链表tmp的下一个节点，保证遍历正确进行
            next = tmp.next;
            //有序链表的临时节点
            ListNode tmpNewNode = newNode.next;
            //寻找带插入节点在有序链表中的插入位置
            //如果比有序链表最前面元素小，就直接在最前面插入
            if (tmp.val <= tmpNewNode.val) {
                tmp.next = newNode.next;
                newNode.next = tmp;
            }else {
                //与下一个节点相比，来的小，插在当前有序链表节点和下一个节点之间，否则算没找到插入位置，继续找
                //这样判断是因为要记录前驱，如果写成tmpNewNode!=null，这时候假设找到位置，前驱就找不到了
                while (tmpNewNode.next != null) {
                    if (tmp.val <= tmpNewNode.next.val){
                        tmp.next = tmpNewNode.next;
                        tmpNewNode.next = tmp;
                        break;
                    }
                    //核心：如果待插入结点大于有序链表当前遍历的节点，只要不是遍历到尾部，就不要在当前节点右边插入
                    // 因为可以在下一轮循环时，把后一个元素当成当前元素来比对
                    // 假设我就是在当前节点后面插入，根据上面的思路，下一轮循环的效果就是在 本轮当前节点（上一轮当前节点的后一个节点）和 本轮前驱（上一轮当前节点的前一个节点之间）插入
                    tmpNewNode = tmpNewNode.next;
                }
                //下一个节点没有元素了，说明当前待插入节点是最大的，直接插在末尾即可
                if (tmpNewNode.next == null) {
                    tmp.next = tmpNewNode.next;
                    tmpNewNode.next = tmp;
                }
            }
            //原链表向下遍历，去下一个待比较元素
            tmp = next;
        }
        listNode.next = newNode.next;
        return listNode.next;
    }

    public static void main(String[] args) {
        //-1->5->3->4->0
        /*ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(1);
        ListNode listNode4 = new ListNode(3);*/

        ListNode listNode1 = new ListNode(3);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(4);

        /*ListNode listNode1 = new ListNode(-1);
        ListNode listNode2 = new ListNode(5);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(0);*/

        SingleLinkedList list1 = new SingleLinkedList();
        list1.add(listNode1);
        list1.add(listNode2);
        list1.add(listNode3);
        //list1.add(listNode4);
        //list1.add(listNode5);
        list1.list();
        ListNode head = insertionSortList(list1.getHead());
        System.out.println();
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        ListNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

class SingleLinkedList {

    //头节点
    private ListNode head = new ListNode(0);

    public ListNode getHead(){
        return head;
    }

    //添加节点到单向链表尾部
    public void add(ListNode heroNode) {
        ListNode temp = head;
        while (true) {
            //找到链表的最后一个节点
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    //显示链表
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        ListNode temp = head.next;

        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }


}
//leetcode submit region end(Prohibit modification and deletion)
